package com.leetcode.algorithm.y19.m04;

import java.util.Stack;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 
 * (done)206. 反转链表
 * (done)203. 移除链表元素
 * (done)328. 奇偶链表
 * (done)234. 回文链表
 * @author: jie.deng
 * @time: 2019年4月16日 上午12:18:44
 */
public class MySolution0413 {
    
    /**
     * 206. 反转链表
     * 反转一个单链表。
     * 
     * 示例:
     * 输入: 1->2->3->4->5->NULL 
     * 输出: 5->4->3->2->1->NULL 
     * 
     * 进阶:
     * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
     * 
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode newHead = head;
        ListNode cur = head;
        while (cur.next != null) {
            // 将cur.next移动到newHead前面
            ListNode todo = cur.next;
            // 1.移出todo
            cur.next = cur.next.next;
            // 2.将todo插入到头结点
            todo.next = newHead;
            newHead = todo;
        }
        return newHead;
    }
    
    /**
     * 203. 移除链表元素
     * 删除链表中等于给定值 val 的所有节点。 
     * 
     * 示例:
     * 输入: 1->2->6->3->4->5->6, val = 6 
     * 输出: 1->2->3->4->5
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode ret = new ListNode(0); // 哨兵结点
        ret.next = head;
        ListNode pre = ret;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = pre.next;
            }
            cur = cur.next;
        }
        return ret.next;
    }
    
    /**
     * 328. 奇偶链表
     * 
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     * 
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     * 
     * 示例 1:
     * 
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * 示例 2:
     * 
     * 输入: 2->1->3->5->6->4->7->NULL 
     * 输出: 2->3->6->7->1->5->4->NULL
     * 说明:
     * 
     * 应当保持奇数节点和偶数节点的相对顺序。
     * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode oddTail = head;
        ListNode evenHead = head.next;
        ListNode evenTail = head.next;
        ListNode cur = head.next.next; // 初始指向第三个节点
        boolean odd = true;
        while (cur != null) {
            ListNode todo = cur;
            cur = cur.next;
            if (odd) {
                evenTail.next = todo.next;
                evenTail = todo.next;
                todo.next = evenHead;
                oddTail.next = todo;
                oddTail = todo;
            }
            odd = !odd;
        }
        return head;
    }
    
    /**
     * 234. 回文链表
     * 
     * 请判断一个链表是否为回文链表。
     * 
     * 示例 1:
     * 
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     * 
     * 输入: 1->2->2->1
     * 输出: true
     * 进阶：
     * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode cur = head;
        Stack<Integer> stack = new Stack<Integer>();
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }

        cur = head;
        while (!stack.isEmpty()) {
            if (stack.pop() != cur.val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
    
}
